package codeTop;

import java.util.Map;

public class q300 {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int max = 1;
        for (int i = 1; i <n ; i++) {
            int idx = binaryInsert(dp, nums[i], 0, max);
            dp[idx] = nums[i];
            max = Math.max(max,idx+1);
        }
        return max;
    }
    int binaryInsert(int[] dp,int target,int l,int r){
        while (l < r) {
            int mid = l+(r-l)/2;
            if (dp[mid] < target) {
                l = mid+1;
            }else {
                r = mid;
            }
        }
        return l;
    }

    public static void main(String[] args) {
        q300 q = new q300();
        System.out.println(q.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
    }
}
